

		LA ORA DE GERMANA - SOLUTIE
	       -----------------------------

	Solutia se bazeaza pe observatia ca daca cuvintele au aceeasi lungime atunci se poate apli-
ca principiul optimalitatii. Problema se reduce la a determina intr-un graf un drum prin K noduri,
de cost maxim si care poate contine cicluri. Nodurile corespund cuvintelor, iar costul muchiei
care leaga nodul I de nodul J este lungimea maxima a unui prefix din J care este sufix in I (cu
alte cuvinte, cat poate "patrunde" cuvantul I in cuvantul J).

OBSERVATIE: Avem muchii si din I in I pentru orice I.

	Aplicam metoda programarii dinamice, astfel: notam cu A[I,J] costul maxim al unui drum care
trece prin I noduri si ajunge in J. Avem conditiile initiale A[0,J]=0 si relatia de recurenta:

A[I,J]:=max(A[I-1,L]+D[L,J]) , L=1,..,N.

	Complexitatea algoritmului este O(N^2 * (K+Ti)), unde Ti este timpul necesar detrminarii u-
nei :intersectii" intre doua cuvinte. Acest lucru poate fi realizat trivial in O(L^2), dar se poate
realiza si in O(L) folosind metoda de determinare a unui prefix-sufix maxim din algoritmul KMP pe
cyvantul obtinut prin alaturarea celor doua cuvinte, respctiv pe un singur cuvant in cazul unei
bucle I->I. 